{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0  0]\n",
      " [ 0 -1]\n",
      " [ 1  1]\n",
      " [-1  0]\n",
      " [ 0  1]]\n",
      "[#sample, #dim]:\n",
      " (5, 2)\n"
     ]
    }
   ],
   "source": [
    "X = np.array([\n",
    "    [0, 0],\n",
    "    [0,-1],\n",
    "    [1, 1],\n",
    "    [-1, 0],\n",
    "    [0,1]\n",
    "])\n",
    "print(X)\n",
    "print(\"[#sample, #dim]:\\n\", X.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  1  1 -1 -1]\n"
     ]
    }
   ],
   "source": [
    "Y = np.array([1, 1,1, -1, -1])\n",
    "print(Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数据可视化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x7fee967652d0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAD8CAYAAABzTgP2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAGQlJREFUeJzt3X+QHOV95/H3B8m7CnYBElrbAkmWiBUDuVyEM5bxObExRiBTFYkkMhYVgnBwKXDBV3XEKYsjVXG4uA7Hf4BToQorBiNwCrAVu1gKOzrx61xxLKxRjNEPSmglLmYtGckIsEG/kPS9P/rZo5/VzP5Qz8xqpc+ramq6n366+8uzrf1s9/TQigjMzMwGnDLWBZiZ2fHFwWBmZhkHg5mZZRwMZmaWcTCYmVnGwWBmZhkHg5mZZRwMZmaWcTCYmVlm4lgXcCymTp0as2bNGusyzMzGlfXr1/8iInqG6zcug2HWrFnU6/WxLsPMbFyR9B8j6edLSWZmlnEwmJlZxsFgZmYZB4OZmWUcDGZmlnEwmJlZpiXBIOkeSbskbWyyXJL+XlKfpGclvb+0bKmkrem1tBX1mHXSkSPwla/A7NkwZQosXgzbto11VXZC2LsXli+HadOgpwduuAFefrntu1UrHu0p6SPA68B9EfGfGiy/HPgscDnwQeArEfFBSVOAOlADAlgP/E5EvDLU/mq1Wvh7DHa8uP56uP/+4t8wwCmnwGmnwaZNcNZZY1ubjWMR8Lu/C//+77B/f9HW1QUzZ8LGjdDdPepNSlofEbXh+rXkjCEivg/sGaLLIorQiIhYC5whaRpwGbAmIvakMFgDLGhFTWad8POfw733vhUKUJxB7N0Ld9wxZmXZieBf/xWeffatUAA4eLA46L797bbuulOfMZwNvFia709tzdrNxoVNm2DSpKPbDx6Ef/u3ztdjJ5Af/xjefPPo9tdfh3Xr2rrrTgWDGrTFEO1Hb0BaJqkuqb579+6WFmd2rGbNKkJgsAkT4NxzO16OnUhmzy4uHQ126qnw3ve2ddedCoZ+YEZpfjqwY4j2o0TEioioRUStp2fY/weUWUf8+q8Xl4EHX+7t7oabbhqbmuwE8YlPFHczTJjwVptUHFx//Mdt3XWngqEXuCbdnXQh8FpE7ARWA5dKmixpMnBpajMbN779bfjkJ4t/r11dRVg88gicf/5YV2bj2sSJ8IMfwEUXwdveVrw+8IGi7fTT27rrVt2V9ABwETAVeAn4a+BtABFxlyQB/0DxwfJe4NMRUU/r/inwP9KmvhgRXx9uf74ryY5H+/fDvn1wxhnFH3ZmLfPGG3D4cHG7WwUjvSupJcHQaQ4GM7PR6+jtqmZmduJwMJiZWcbBYGZmGQeDmZllHAxmZpZxMJiZWcbBYGZmGQeDmZllHAxmZpZxMJiZWcbBYGZmGQeDmZllHAxmZpZxMJiZWcbBYGZmmZYEg6QFkrZI6pO0vMHy2yU9k17PS3q1tOxwaVlvK+oxM7NjN7HqBiRNAO4E5lM8w3mdpN6I2DzQJyL+e6n/Z4ELSpvYFxFzq9ZhZmat0YozhnlAX0Rsj4iDwIPAoiH6XwU80IL9mplZG7QiGM4GXizN96e2o0h6DzAbeKLUPElSXdJaSVe0oB4zM6ug8qUkoNFjz5s9SHoJsCoiDpfaZkbEDknnAE9I2hAR247aibQMWAYwc+bMqjWbmVkTrThj6AdmlOanAzua9F3CoMtIEbEjvW8HniL//KHcb0VE1CKi1tPTU7VmMzNrohXBsA6YI2m2pC6KX/5H3V0k6X3AZOCHpbbJkrrT9FTgw8DmweuamVnnVL6UFBGHJN0IrAYmAPdExCZJtwL1iBgIiauAByOifJnpPOCrko5QhNRt5buZzMys85T/nh4farVa1Ov1sS7DzGxckbQ+ImrD9fM3n83MLONgMDOzjIPBzMwyDgYzM8s4GMzMLONgMDOzjIPBzMwyDgYzM8s4GMzMLONgMDOzjIPBzMwyDgYzM8s4GMzMLONgMDOzjIPBzMwyDgYzM8u0JBgkLZC0RVKfpOUNll8rabekZ9LrM6VlSyVtTa+lrajHzMyOXeVHe0qaANwJzAf6gXWSehs8ovOhiLhx0LpTgL8GakAA69O6r1Sty8zMjk0rzhjmAX0RsT0iDgIPAotGuO5lwJqI2JPCYA2woAU1mZnZMWpFMJwNvFia709tg/2RpGclrZI0Y5TrImmZpLqk+u7du1tQtpmZNdKKYFCDthg0/wgwKyL+M/AYsHIU6xaNESsiohYRtZ6enmMu1szMhtaKYOgHZpTmpwM7yh0i4uWIOJBm/xH4nZGua2ZmndWKYFgHzJE0W1IXsAToLXeQNK00uxB4Lk2vBi6VNFnSZODS1GZmZmOk8l1JEXFI0o0Uv9AnAPdExCZJtwL1iOgF/pukhcAhYA9wbVp3j6T/SREuALdGxJ6qNZmZ2bFTRMNL+se1Wq0W9Xp9rMswMxtXJK2PiNpw/fzNZzMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7NMS4JB0gJJWyT1SVreYPlNkjZLelbS45LeU1p2WNIz6dU7eF0zM+usyk9wkzQBuBOYT/EM53WSeiNic6nbj4FaROyVdAPwd8Cn0rJ9ETG3ah1mZtYarThjmAf0RcT2iDgIPAgsKneIiCcjYm+aXQtMb8F+zcysDVoRDGcDL5bm+1NbM9cB3yvNT5JUl7RW0hUtqMfMzCqofCkJUIO2hg+SlnQ1UAM+WmqeGRE7JJ0DPCFpQ0Rsa7DuMmAZwMyZM6tXbWZmDbXijKEfmFGanw7sGNxJ0iXALcDCiDgw0B4RO9L7duAp4IJGO4mIFRFRi4haT09PC8o2M7NGWhEM64A5kmZL6gKWANndRZIuAL5KEQq7Su2TJXWn6anAh4Hyh9ZmZtZhlS8lRcQhSTcCq4EJwD0RsUnSrUA9InqBLwPvAL4lCeCnEbEQOA/4qqQjFCF126C7mczMrMMU0fDjgONarVaLer0+1mWYmY0rktZHRG24fv7ms5mZZRwMZmaWcTCYmVnGwWBmZhkHg5mZZRwMZmaWcTCYmVnGwWBmZhkHg5mZZRwMZmaWcTCYmVnGwWBmZhkHg5mZZRwMZmaWcTCYmVmmJcEgaYGkLZL6JC1vsLxb0kNp+dOSZpWW3Zzat0i6rBX1NHP4MPzLv8Bdd8GPfgTj8FEUdrzatw9WrYIVK2Dr1rGuxqySyk9wkzQBuBOYT/H853WSegc9ie064JWIeK+kJcCXgE9JOp/iUaC/CZwFPCbpNyLicNW6BvvZz+D3fg9+8Qs4dAhOOQUuvBAefRS6u1u9NzuprF8P8+cXB9bhw8VfHNdeC3feCcUTC83GlVacMcwD+iJie0QcBB4EFg3qswhYmaZXAR9X8YzPRcCDEXEgIl4A+tL2Wu5P/gR++lP41a+KP+7eeAN+8AO47bZ27M1OGkeOwO//PrzySnFw7d1bHGD33QcPPzzW1Zkdk1YEw9nAi6X5/tTWsE9EHAJeA84c4bqVvfZaEQKHB52H7N8Pd9/d6r3ZSWXdOnj99aPb33ijuKxkNg61IhganSsPvnrfrM9I1i02IC2TVJdU371796gKPHSo+bKDB0e1KbPcgQPNLxft29fZWsxapBXB0A/MKM1PB3Y06yNpInA6sGeE6wIQESsiohYRtZ6enlEVeOaZcO65R7d3dcHixaPalFnugx9s3H7qqXD11Z2txaxFWhEM64A5kmZL6qL4MLl3UJ9eYGmaXgw8ERGR2peku5ZmA3OAH7WgpqPcdx+cdhr82q8V829/O0yfDn/zN+3Ym500urvh/vuLA6urq2h7xztg3jy45pqxrc3sGFW+KykiDkm6EVgNTADuiYhNkm4F6hHRC9wN3C+pj+JMYUlad5OkbwKbgUPAn7fjjiSA3/5t2LatCIitW+FDH4Irr4RJk9qxNzupLFwImzfDvffC7t2wYAFcfjlMmDDWlZkdE8U4vJm/VqtFvV4f6zLMzMYVSesjojZcP3/z2czMMg4GMzPLOBjMzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs0ylYJA0RdIaSVvT++QGfeZK+qGkTZKelfSp0rJ7Jb0g6Zn0mlulHjMzq67qGcNy4PGImAM8nuYH2wtcExG/CSwA7pB0Rmn5X0bE3PR6pmI9ZmZWUdVgWASsTNMrgSsGd4iI5yNia5reAewCeiru18zM2qRqMLwrInYCpPd3DtVZ0jygC9hWav5iusR0u6TuIdZdJqkuqb579+6KZZuZWTPDBoOkxyRtbPBaNJodSZoG3A98OiKOpOabgXOBDwBTgM83Wz8iVkRELSJqPT0+4TAza5eJw3WIiEuaLZP0kqRpEbEz/eLf1aTfacCjwF9FxNrStnemyQOSvg58blTVm5lZy1W9lNQLLE3TS4GHB3eQ1AV8B7gvIr41aNm09C6Kzyc2VqzHzMwqqhoMtwHzJW0F5qd5JNUkfS31uRL4CHBtg9tS/0nSBmADMBX424r1mJlZRYqIsa5h1Gq1WtTr9bEuw8xsXJG0PiJqw/XzN5/NzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs4yDwczMMg4GMzPLOBjMzCzjYDAzs4yDwczMMpWCQdIUSWskbU3vk5v0O1x6SE9vqX22pKfT+g+lp72ZmdkYqnrGsBx4PCLmAI+n+Ub2RcTc9FpYav8ScHta/xXguor1mJlZRVWDYRGwMk2vpHhu84ik5zxfDKw6lvXNzKw9qgbDuyJiJ0B6f2eTfpMk1SWtlTTwy/9M4NWIOJTm+4GzK9ZjZmYVTRyug6THgHc3WHTLKPYzMyJ2SDoHeELSBuCXDfo1fQC1pGXAMoCZM2eOYtdmZjYawwZDRFzSbJmklyRNi4idkqYBu5psY0d63y7pKeAC4J+BMyRNTGcN04EdQ9SxAlgBUKvVmgaImZlVU/VSUi+wNE0vBR4e3EHSZEndaXoq8GFgc0QE8CSweKj1zcyss6oGw23AfElbgflpHkk1SV9Lfc4D6pJ+QhEEt0XE5rTs88BNkvooPnO4u2I9ZmZWkYo/3MeXWq0W9Xp9rMswMxtXJK2PiNpw/fzNZzMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMws42AwM7OMg8HMzDKVgkHSFElrJG1N75Mb9PmYpGdKr/2SrkjL7pX0QmnZ3Cr1mJlZdVXPGJYDj0fEHODxNJ+JiCcjYm5EzAUuBvYC/7vU5S8HlkfEMxXrMTOziqoGwyJgZZpeCVwxTP/FwPciYm/F/ZqZWZtUDYZ3RcROgPT+zmH6LwEeGNT2RUnPSrpdUnezFSUtk1SXVN+9e3e1qs3MrKlhg0HSY5I2NngtGs2OJE0DfgtYXWq+GTgX+AAwBfh8s/UjYkVE1CKi1tPTM5pdm5nZKEwcrkNEXNJsmaSXJE2LiJ3pF/+uITZ1JfCdiHiztO2dafKApK8Dnxth3WZm1iZVLyX1AkvT9FLg4SH6XsWgy0gpTJAkis8nNlasx8zMKqoaDLcB8yVtBeaneSTVJH1toJOkWcAM4P8MWv+fJG0ANgBTgb+tWI+ZmVU07KWkoUTEy8DHG7TXgc+U5v8vcHaDfhdX2b+ZmbWev/lsZmYZB4OZmWUcDGZmlnEwmJlZxsFgZmYZB4OZmWUcDGZmlnEwmJlZxsFgZmYZB4OZmWUcDGZmlnEwmJlZxsFgZmYZB4OZmWUcDGZmlqkUDJI+KWmTpCOSakP0WyBpi6Q+SctL7bMlPS1pq6SHJHVVqcdsTBw+DF/+MsyYAaefDosWwfPPj3VVZses6hnDRuAPge836yBpAnAn8AngfOAqSeenxV8Cbo+IOcArwHUV6zHrvD/7M/jCF6C/H375S3jkEZg3r5g3G4cqBUNEPBcRW4bpNg/oi4jtEXEQeBBYlJ7zfDGwKvVbSfHcZ7PxY+dO+MY3YO/et9oiYN8+uOOOsavLrIJOfMZwNvBiab4/tZ0JvBoRhwa1m40fmzfDpElHtx88CGvXdr4esxYY9pnPkh4D3t1g0S0R8fAI9qEGbTFEe7M6lgHLAGbOnDmC3Zp1wOzZcODA0e0TJ8J553W+HrMWGDYYIuKSivvoB2aU5qcDO4BfAGdImpjOGgbam9WxAlgBUKvVmgaIWUedcw5cdBE89RTs3/9We1cX/MVfjFVVZpV04lLSOmBOugOpC1gC9EZEAE8Ci1O/pcBIzkDMji+rVsFVV0F3d3GmcO658N3vFu9m41DV21X/QFI/8CHgUUmrU/tZkr4LkM4GbgRWA88B34yITWkTnwduktRH8ZnD3VXqMRsTb3873HMP/OpXsGcPPPccfPSjY12V2TFT8Yf7+FKr1aJer491GWZm44qk9RHR9DtnA/zNZzMzyzgYzMws42AwM7OMg8HMzDIOBjMzyzgYzMwsMy5vV5W0G/iPCpuYSvHN6+ON6xqd47Gu47EmcF2jcTzWBK2p6z0R0TNcp3EZDFVJqo/kXt5Oc12jczzWdTzWBK5rNI7HmqCzdflSkpmZZRwMZmaWOVmDYcVYF9CE6xqd47Gu47EmcF2jcTzWBB2s66T8jMHMzJo7Wc8YzMysiRM2GCR9UtImSUckNf0kX9ICSVsk9UlaXmqfLelpSVslPZSeJdGKuqZIWpO2u0bS5AZ9PibpmdJrv6Qr0rJ7Jb1QWja3U3WlfodL++4ttbd8vEY4VnMl/TD9rJ+V9KnSspaOVbNjpbS8O/2396WxmFVadnNq3yLpsip1jLKmmyRtTmPzuKT3lJY1/Fl2qK5rJe0u7f8zpWVL0898q6SlHa7r9lJNz0t6tbSsLeMl6R5JuyRtbLJckv4+1fyspPeXlrVnrCLihHwB5wHvA54Cak36TAC2AecAXcBPgPPTsm8CS9L0XcANLarr74DlaXo58KVh+k8B9gCnpvl7gcVtGK8R1QW83qS95eM1kpqA3wDmpOmzgJ3AGa0eq6GOlVKf/wrclaaXAA+l6fNT/25gdtrOhA7V9LHSsXPDQE1D/Sw7VNe1wD80Od63p/fJaXpyp+oa1P+zwD0dGK+PAO8HNjZZfjnwPYrHIV8IPN3usTphzxgi4rmI2DJMt3lAX0Rsj4iDwIPAIkkCLgZWpX4rgStaVNqitL2Rbncx8L2I2Nui/Tcz2rr+vzaO17A1RcTzEbE1Te8AdgHDfoHnGDQ8VoaodxXw8TQ2i4AHI+JARLwA9KXttb2miHiydOyspXiEbruNZKyauQxYExF7IuIVYA2wYIzqugp4oEX7bioivk/xx18zi4D7orCW4pHI02jjWJ2wwTBCZwMvlub7U9uZwKtRPH2u3N4K74qInQDp/Z3D9F/C0QfnF9Mp5e2Sujtc1yRJdUlrBy5v0b7xGtVYSZpH8ZfgtlJzq8aq2bHSsE8ai9coxmYk67arprLrKP7yHNDoZ9kKI63rj9LPZpWkgefCt2usRrXtdMltNvBEqbld4zWcZnW3bawmtmIjY0XSY8C7Gyy6JSJG8vxoNWiLIdor1zXSbaTtTAN+i+KxqANuBn5O8QtwBcXjUW/tYF0zI2KHpHOAJyRtAH7ZoN+IxqvFY3U/sDQijqTmYx6rRrto0Db4v7Etx9MQRrxdSVcDNaD8zNGjfpYRsa3R+m2o6xHggYg4IOl6ijOti0e4bjvrGrAEWBURh0tt7Rqv4XT6uBrfwRARl1TcRD8wozQ/HdhB8f8jOUPSxPSX30B75bokvSRpWkTsTL/Mdg2xqSuB70TEm6Vt70yTByR9HfhcJ+tKl2uIiO2SngIuAP6ZYxyvVtQk6TTgUeCv0qn2wLaPeawaaHasNOrTL2kicDrFJYKRrNuumpB0CUXQfjQiDgy0N/lZtuIX3bB1RcTLpdl/BL5UWveiQes+1YKaRlRXyRLgz8sNbRyv4TSru21jdbJfSloHzFFxR00XxcHQG8UnO09SXN8HWAqM5AxkJHrT9kay3aOucaZfkAPX9a8AGt7J0I66JE0euBwjaSrwYWBzG8drJDV1Ad+huAb7rUHLWjlWDY+VIepdDDyRxqYXWKLirqXZwBzgRxVqGXFNki4AvgosjIhdpfaGP8sW1DTSuqaVZhcCz6Xp1cClqb7JwKXkZ8xtrSvV9j6KD3N/WGpr53gNpxe4Jt2ddCHwWvqjp31j1Y5P2Y+HF/AHFIl6AHgJWJ3azwK+W+p3OfA8RfLfUmo/h+Ifbx/wLaC7RXWdCTwObE3vU1J7Dfhaqd8s4GfAKYPWfwLYQPFL7hvAOzpVF/Bf0r5/kt6va+d4jbCmq4E3gWdKr7ntGKtGxwrFpamFaXpS+m/vS2NxTmndW9J6W4BPtPA4H66mx9LxPzA2vcP9LDtU1/8CNqX9PwmcW1r3T9MY9gGf7mRdaf4LwG2D1mvbeFH88bczHcf9FJ8FXQ9cn5YLuDPVvIHSXZbtGit/89nMzDIn+6UkMzMbxMFgZmYZB4OZmWUcDGZmlnEwmJlZxsFgZmYZB4OZmWUcDGZmlvl/z4eDmSKxwTwAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "c_seq = [\" rb\"[y] for y in Y]\n",
    "plt.scatter(X[:, 0], X[:, 1], c=c_seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# $A(\\alpha)=\\sum_{i=1}^{n}\\alpha_i - \\frac{1}{2}\\sum_{i=1}^{n}\\sum_{j=1}^{n}\\alpha_i\\alpha_j y_i y_j x_i^T x_j$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$x_i^T x_j$ 矩阵\n",
    "- 代码中 X 排成**行**向量，同公式**相反**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dot(x, xT):\n",
      " [[ 0  0  0  0  0]\n",
      " [ 0  1 -1  0 -1]\n",
      " [ 0 -1  2 -1  1]\n",
      " [ 0  0 -1  1  0]\n",
      " [ 0 -1  1  0  1]]\n"
     ]
    }
   ],
   "source": [
    "xx = np.dot(X, X.T)\n",
    "print(\"dot(x, xT):\\n\", xx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$y_i y_j$ 矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yy:\n",
      " [[ 1  1  1 -1 -1]\n",
      " [ 1  1  1 -1 -1]\n",
      " [ 1  1  1 -1 -1]\n",
      " [-1 -1 -1  1  1]\n",
      " [-1 -1 -1  1  1]]\n"
     ]
    }
   ],
   "source": [
    "yy = np.multiply(\n",
    "    np.expand_dims(Y, axis=1),\n",
    "    np.expand_dims(Y, axis=0)\n",
    ")\n",
    "print(\"yy:\\n\", yy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$y_i y_j x_i^T x_j$ 矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yyxx:\n",
      " [[ 0  0  0  0  0]\n",
      " [ 0  1 -1  0  1]\n",
      " [ 0 -1  2  1 -1]\n",
      " [ 0  0  1  1  0]\n",
      " [ 0  1 -1  0  1]]\n"
     ]
    }
   ],
   "source": [
    "yyxx = np.multiply(xx, yy)\n",
    "print(\"yyxx:\\n\", yyxx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\alpha_i \\alpha_j$ 系数，即 $y_i y_j x_i^T x_j$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 2): 1\n",
      "(2, 3): -2\n",
      "(2, 5): 2\n",
      "(3, 3): 2\n",
      "(3, 4): 2\n",
      "(3, 5): -2\n",
      "(4, 4): 1\n",
      "(5, 5): 1\n",
      "#non zero: 8\n"
     ]
    }
   ],
   "source": [
    "nonzero_coef = []  # (i, j, coff_ij)\n",
    "\n",
    "for i in range(X.shape[0]):\n",
    "    for j in range(i, X.shape[0]):\n",
    "        coef = yyxx[i][j]\n",
    "        if i != j:\n",
    "            coef += yyxx[j][i] # 对称，除了对角线不双倍\n",
    "        if coef != 0:\n",
    "            print(\"({}, {}): {}\".format(i+1, j+1, coef))\n",
    "            nonzero_coef.append((i, j, coef))\n",
    "#     print('\\n')\n",
    "print(\"#non zero:\", len(nonzero_coef))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 求 $\\alpha_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "约束包括：\n",
    "- $\\sum_{i=1}^{n} y_i \\alpha_i=0$\n",
    "- $\\frac{\\partial A(\\alpha)}{\\partial\\alpha_i}=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "constrains = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\sum_{i=1}^{n} y_i \\alpha_i=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "α1 + α2 + α3 - α4 - α5\n"
     ]
    }
   ],
   "source": [
    "def sgn(x):\n",
    "    return '-' if x < 0 else '+'\n",
    "\n",
    "con_ya = \"-α1\" if Y[0] < 0 else \"α1\"\n",
    "for i in range(1, Y.shape[0]):\n",
    "    con_ya += \" {} α{}\".format(sgn(Y[i]), i+1)\n",
    "    \n",
    "print(con_ya)\n",
    "constrains.append(\"{} = 0\".format(con_ya))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "各 $\\frac{\\partial A(\\alpha)}{\\partial\\alpha_i}=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "partial:\n",
      "1: 1\n",
      "2: 1 - 1α2 + (2/2)α3 - (2/2)α5\n",
      "3: 1 + (2/2)α2 - 2α3 - (2/2)α4 + (2/2)α5\n",
      "4: 1 - (2/2)α3 - 1α4\n",
      "5: 1 - (2/2)α2 + (2/2)α3 - 1α5\n"
     ]
    }
   ],
   "source": [
    "def sgn_rev(x):\n",
    "    \"\"\"符号反转，因为上述 A(α) 第二项带负号\"\"\"\n",
    "    return '-' if x > 0 else '+'\n",
    "\n",
    "print(\"partial:\")\n",
    "for i in range(X.shape[0]):\n",
    "    # 上述 A(α) 第一项的偏导\n",
    "    part = \"1\"\n",
    "    # 第二项的\n",
    "    for cf in nonzero_coef:\n",
    "        if i in cf[:2]:  # 涉及 α_i\n",
    "            # 另一个编号\n",
    "            other = cf[1] if i == cf[0] else cf[0]\n",
    "            # 偏导符号\n",
    "            part_sign = sgn_rev(cf[-1])\n",
    "            # 偏导系数绝对值\n",
    "            coef = abs(cf[-1])\n",
    "            if cf[0] == cf[1]:  # 平方项\n",
    "                part_coef = str(coef)  # * 2 / 2\n",
    "            else:\n",
    "                part_coef = \"({}/2)\".format(coef)\n",
    "            part += \" {} {}α{}\".format(\n",
    "                part_sign, part_coef, other+1)\n",
    "    # 综上\n",
    "    print(\"{}: {}\".format(i+1, part))\n",
    "    constrains.append(\"{} = 0\".format(part))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "constrains:\n",
      "α1 + α2 + α3 - α4 - α5 = 0\n",
      "1 = 0\n",
      "1 - 1α2 + (2/2)α3 - (2/2)α5 = 0\n",
      "1 + (2/2)α2 - 2α3 - (2/2)α4 + (2/2)α5 = 0\n",
      "1 - (2/2)α3 - 1α4 = 0\n",
      "1 - (2/2)α2 + (2/2)α3 - 1α5 = 0\n"
     ]
    }
   ],
   "source": [
    "print(\"constrains:\")\n",
    "for con in constrains:\n",
    "    print(con)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 然后手算 $\\alpha_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "α: [0.   1.   0.75 0.25]\n"
     ]
    }
   ],
   "source": [
    "# 算到的 α\n",
    "alpha = np.array([0, 1, 0.75, 0.25])\n",
    "print(\"α:\", alpha)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# $W^{*}=\\sum_{i=1}^{n}\\alpha_i y_i x_i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "index 4 is out of bounds for axis 0 with size 4",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-15-30ff1a3b8b05>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mW_star\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mX\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshape\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0mW_star\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mW_star\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0malpha\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mY\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mX\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"W*:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mW_star\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: index 4 is out of bounds for axis 0 with size 4"
     ]
    }
   ],
   "source": [
    "W_star = 0\n",
    "for i in range(X.shape[0]):\n",
    "    W_star = W_star + alpha[i] * Y[i] * X[i]\n",
    "print(\"W*:\", W_star)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "选支持向量 $x^+$ 和 $x^-$：$\\alpha_i\\neq0$就是支持向量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x+: [1 0]\n",
      "x-: [2 0]\n"
     ]
    }
   ],
   "source": [
    "x_pos_id, x_neg_id = -1, -1\n",
    "\n",
    "for i in range(X.shape[0]):\n",
    "    if alpha[i] != 0:\n",
    "        if Y[i] == -1 and x_neg_id == -1:\n",
    "            x_neg_id = i\n",
    "        if Y[i] == 1 and x_pos_id == -1:\n",
    "            x_pos_id = i\n",
    "\n",
    "x_pos = X[x_pos_id]\n",
    "x_neg = X[x_neg_id]\n",
    "\n",
    "print(\"x+:\", x_pos)\n",
    "print(\"x-:\", x_neg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$b^*=-\\frac{1}{2}W^{*T}(x^+ + x^-)$\n",
    "- $x^+$ 和 $x^-$ 是正负例各一个支持向量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b*: 0.75\n"
     ]
    }
   ],
   "source": [
    "b_star = -0.5 * np.dot(W_star, (x_pos + x_neg).T)\n",
    "print(\"b*:\", b_star)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最优分类面：$W^{*T}x+b^*=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "plane: - 0.5x1 - 0.5x2 + 0.75 = 0\n"
     ]
    }
   ],
   "source": [
    "plane = \"\"\n",
    "\n",
    "# W*\n",
    "for i in range(W_star.shape[0]):\n",
    "    plane += \"{} {}x{} \".format(\n",
    "        sgn(W_star[i]), abs(W_star[i]), i+1)\n",
    "\n",
    "# b*\n",
    "plane += \"{} {} = 0\".format(sgn(b_star), b_star)\n",
    "\n",
    "print(\"plane:\", plane)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
